# Definition for singly-linked list.
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    # def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    #
    #
    #     if list1 is None and list2 is None:
    #         return None
    #     if list1 is None:
    #         return list2
    #     if list2 is None:
    #         return list1
    #     if list1.val>list2.val:
    #         list1,list2=list2,list1
    #     node1flag1 = list1
    #     node1flag2 = list1.next
    #     node2flag1 = list2
    #     node2flag2 = list2.next
    #
    #     while node1flag2 and node2flag2:
    #         print("node1flag2.val:",node1flag2.val)
    #         print("node2flag2.val:",node2flag2.val)
    #         if (node1flag2.val < node2flag1.val):
    #             node1flag1.next = node1flag2
    #             node1flag1 = node1flag2
    #             node1flag2 = node1flag2.next
    #
    #
    #         else:
    #             node1flag1.next = node2flag1
    #             node1flag1 = node1flag1.next
    #
    #             node2flag1 = node1flag2
    #             node1flag2 = node1flag1.next
    #             node2flag2 = node2flag1.next
    #
    #
    #
    #     if(node2flag1!=None):
    #         node1flag1.next = node2flag1
    #     if(node1flag2!=None):
    #         node1flag1.next = node1flag2
    #
    #
    #     return list1
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        current = ListNode(0, None)
        result = current
        while list1 and list2:
            if (list1.val <= list2.val):
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next

            current = current.next

        if (list1):
            current.next = list1
        if (list2):
            current.next = list2
        result = result.next

        return result


# node7 = ListNode(7, None)
node6 = ListNode(4, None)
node4 = ListNode(3, node6)
node11 = ListNode(1, node4)

# node5 = ListNode(5, None)
node3 = ListNode(4, None)
node2 = ListNode(2, node3)
node1 = ListNode(1, node2)

lll = Solution()
lll2 = lll.mergeTwoLists(node11, node1)

while lll2:
    print(lll2.val)
    lll2 = lll2.next
